/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package compilador;

import java.util.*;
import java.util.Stack;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 *
 * @author Melinton
 */
public class Parser 
{
    //--------------------------------------------------------------------------
    // ATRIBUTOS
    //--------------------------------------------------------------------------
    ArrayList<String> regex;
    Stack<Operador> tokens;    
    HashMap pp;
    HashMap sp;
    int contadorEstados;    
    
    //--------------------------------------------------------------------------
    // CONSRTUCTOR
    //--------------------------------------------------------------------------
    public Parser()
    {
        regex = new ArrayList();
        tokens = new Stack();
        pp = new HashMap();
        sp = new HashMap();
        contadorEstados = 0;        
    }
    
    //--------------------------------------------------------------------------
    // MÉTODOS
    //--------------------------------------------------------------------------
    public ArrayList<String> convertirAPosfix(String cadena) 
    {
        
        try {
            if(validarCadena(cadena))
                parsearCadena(cadena);
        } catch (Exception ex) {
            Logger.getLogger(Parser.class.getName()).log(Level.SEVERE, null, ex);            
        }             
        
        return regex;
    }
    
    public void parsearCadena(String cadena) throws Exception
    {   
        //validarCadena(cadena);
        for(int i=0; i<cadena.length(); i++)
        {
            int a = (i>0)?(i-1):i;
            if(cadena.charAt(i) == '(')
            {                
                if(a>=0&&a!=i)
                {
                    while(!tokens.isEmpty() && (tokens.peek().darPrioridad()>=0))
                    {
                        regex.add(tokens.pop().darValor());                        
                    }
                    if(i>0)
                    {
                        if(cadena.charAt(i-1)!='|' || cadena.charAt(i-1)!='(')//if(cadena.charAt(i-1)==')' || cadena.charAt(i-1)=='*' || Character.isLetterOrDigit(cadena.charAt(i-1)) || cadena.charAt(i-1)=='#')
                            tokens.push(new Operador(".",0));
                    }
                }
                tokens.push(new Operador("" + cadena.charAt(i), -1));
            }

            else if(cadena.charAt(i)==')')
            {
                while(!tokens.isEmpty() && !tokens.peek().darValor().equals("("))
                {
                    regex.add(tokens.pop().darValor());
                }
                tokens.pop();
            }
            else if(cadena.charAt(i)=='*' || cadena.charAt(i)=='|')
            {
                Operador pivote;
                if(cadena.charAt(i)=='*')
                    pivote = new Operador("" + cadena.charAt(i), 2);
                else
                    pivote = new Operador("" + cadena.charAt(i), 1);
                if(tokens.isEmpty())
                    tokens.push(pivote);
                else
                {
                    while(!tokens.isEmpty() && tokens.peek().darPrioridad()>=pivote.darPrioridad())
                    {
                        regex.add(tokens.pop().darValor());                        
                    }
                    tokens.push(pivote);                    
                }
            }
            else if(Character.isLetterOrDigit(cadena.charAt(i)) || cadena.charAt(i)=='#' || cadena.charAt(i)=='¬')
            {
                if(cadena.charAt(a)!='|' && cadena.charAt(a)!='(' && a>=0 && a!=i)
                {
                    while(!tokens.isEmpty() && (tokens.peek().darPrioridad()>=0))
                    {
                        regex.add(tokens.pop().darValor());                        
                    }
                    tokens.push(new Operador(".",0));
                }
                regex.add("" + cadena.charAt(i));
            }            
        }           
        while(!tokens.isEmpty())
        {
            regex.add(tokens.pop().darValor());
        }
    }
    
    public Node crearArbol()
    {
        Stack<Node> pila = new Stack();
        for(int u=0; u<regex.size(); u++)
        {
            switch(regex.get(u))
            {
                case "*":
                    Node nodo0 = new Node("*");
                    Node nodoHijo0 = pila.pop();
                    nodo0.setHijoIzquierdo(nodoHijo0);
                    nodoHijo0.setPadre(nodo0);
                    pila.push(nodo0);
                    break;                                    
                case "|":
                    Node nodo3 = new Node("|");                    
                    Node nodoHijoIzq;                    
                    Node nodoHijoDer;
                    if(pila.peek().darContenido().equals("."))
                    {
                        nodoHijoIzq = pila.pop();
                        nodoHijoDer = pila.pop();
                    }
                    else                        
                    {
                        nodoHijoDer = pila.pop();
                        nodoHijoIzq = pila.pop();
                    }
                    nodo3.setHijoDerecho(nodoHijoDer);
                    nodo3.setHijoIzquierdo(nodoHijoIzq);
                    nodoHijoIzq.setPadre(nodo3);
                    nodoHijoDer.setPadre(nodo3);
                    pila.push(nodo3);
                    break;
                case ".":
                    Node nodo4 = new Node("."); 
                    Node nodoHijoIzq1;
                    Node nodoHijoDer1;
                    if(pila.peek().darContenido().equals("."))
                    {
                        nodoHijoIzq1 = pila.pop();
                        nodoHijoDer1 = pila.pop();
                    }
                    else                        
                    {
                        nodoHijoDer1 = pila.pop();
                        nodoHijoIzq1 = pila.pop();
                    }                    
                        
                    nodo4.setHijoDerecho(nodoHijoDer1);
                    nodo4.setHijoIzquierdo(nodoHijoIzq1);
                    nodoHijoIzq1.setPadre(nodo4);
                    nodoHijoDer1.setPadre(nodo4);
                    pila.push(nodo4);
                    break;
                default:
                    Node nodo5 = new Node(regex.get(u));
                    pila.push(nodo5);
                    break;
                    
            }
        }
        return pila.pop();
    }
    
    public Automata thompson(Node raiz, ArrayList<String> leng, Estado izquierdaFinal) 
    {        
        switch(raiz.darContenido())
        {            
            case "¬":
                ArrayList<Estado> estadosEp = new ArrayList();                
                ArrayList<Estado> estadosFinales = new ArrayList();
                ArrayList<Funcion> funcionesEp = new ArrayList(); 
                Estado estadoQ_0;
                if(izquierdaFinal!=null)
                    estadoQ_0 = izquierdaFinal;
                else
                    estadoQ_0 = new Estado("S"+contadorEstados);                                
                estadosEp.add(estadoQ_0);
                if(estadoQ_0 != izquierdaFinal)
                    contadorEstados++;                
                Estado estado2 = new Estado("S"+Integer.toString(contadorEstados));
                estadosEp.add(estado2);
                contadorEstados++;      
                estadosFinales.add(estado2);
                funcionesEp.add(new Funcion(estadoQ_0, raiz.darContenido(), estado2));
                Automata a = new Automata(estadoQ_0, estadosEp, estadosFinales, funcionesEp, leng, Automata.AFN);                                 
                return a;
            case "|":
                ArrayList<Estado> estadosOr = new ArrayList();                
                ArrayList<Estado> estadosFinalesOr = new ArrayList();
                ArrayList<Funcion> funcionesOr = new ArrayList();
                Estado orQ_0;
                if(izquierdaFinal!=null)
                    orQ_0 = izquierdaFinal;
                else
                    orQ_0 = new Estado("S"+contadorEstados); 
                if(orQ_0 != izquierdaFinal)
                    contadorEstados++;
                estadosOr.add(orQ_0);
                Automata orIzq = thompson(raiz.darHijoIzquierdo(), leng, null);
                Automata orDer = thompson(raiz.darHijoDerecho(), leng, null);                                
                estadosOr.addAll(orIzq.estados);
                estadosOr.addAll(orDer.estados);
                Estado fin = new Estado("S"+Integer.toString(contadorEstados));
                contadorEstados++;
                estadosFinalesOr.add(fin);
                estadosOr.add(fin);                                
                funcionesOr.add(new Funcion(orQ_0, "¬", orIzq.estadoInicial));
                funcionesOr.add(new Funcion(orQ_0, "¬", orDer.estadoInicial));
                funcionesOr.add(new Funcion(orIzq.estadosFinales.get(0), "¬", fin));
                funcionesOr.add(new Funcion(orDer.estadosFinales.get(0), "¬", fin));                
                funcionesOr.addAll(orIzq.funciones);
                funcionesOr.addAll(orDer.funciones);                          
                Automata or = new Automata(orQ_0, estadosOr, estadosFinalesOr, funcionesOr, leng, Automata.AFD);
                return or;
            case ".":
                ArrayList<Estado> estadosConcat = new ArrayList();                
                ArrayList<Estado> estadosFinalesConcat = new ArrayList();
                ArrayList<Funcion> funcionesConcat = new ArrayList();                
                Automata izq = thompson(raiz.darHijoIzquierdo(), leng, null);
                Automata der = thompson(raiz.darHijoDerecho(), leng, izq.estadosFinales.get(0));
                Estado estadoConcatQ_0 = izq.estadoInicial;
                der.estados.remove(der.estadoInicial);
                //der.estadoInicial = izq.estadosFinales.get(0);                
                estadosConcat.addAll(izq.estados);
                estadosConcat.addAll(der.estados);
                estadosFinalesConcat.add(der.estadosFinales.get(0));
                funcionesConcat.addAll(izq.funciones);
                funcionesConcat.addAll(der.funciones);                 
                Automata concat = new Automata(estadoConcatQ_0, estadosConcat, estadosFinalesConcat, funcionesConcat, leng, Automata.AFN);
                return concat;
            case "*":
                ArrayList<Estado> estadosKleene = new ArrayList();                
                ArrayList<Estado> estadosFinalesKleene = new ArrayList();
                ArrayList<Funcion> funcionesKleene = new ArrayList();
                Estado estadoKleeneQ_0;
                if(izquierdaFinal!=null)
                    estadoKleeneQ_0 = izquierdaFinal;
                else
                    estadoKleeneQ_0 = new Estado("S"+contadorEstados);                
                estadosKleene.add(estadoKleeneQ_0);
                if(estadoKleeneQ_0 != izquierdaFinal)
                    contadorEstados++;                                
                Automata c = thompson(raiz.darHijoIzquierdo(), leng, null);
                estadosKleene.addAll(c.estados);
                Estado estadoKleeneFinal = new Estado("S"+contadorEstados);
                estadosFinalesKleene.add(estadoKleeneFinal);
                estadosKleene.add(estadoKleeneFinal);
                contadorEstados++;                
                funcionesKleene.add(new Funcion(estadoKleeneQ_0, "¬", c.estadoInicial));
                funcionesKleene.add(new Funcion(estadoKleeneQ_0, "¬", estadoKleeneFinal));
                funcionesKleene.add(new Funcion(c.estadosFinales.get(0), "¬", c.estadoInicial));
                funcionesKleene.add(new Funcion(c.estadosFinales.get(0), "¬", estadoKleeneFinal));                
                funcionesKleene.addAll(c.funciones);                
                Automata kleene = new Automata(estadoKleeneQ_0, estadosKleene, estadosFinalesKleene, funcionesKleene, leng, Automata.AFN);
                return kleene;
            default:                
                ArrayList<Estado> estadosDef = new ArrayList();                
                ArrayList<Estado> estadosFinalesDef = new ArrayList();
                ArrayList<Funcion> funcionesDef = new ArrayList();
                Estado defQ_0;
                if(izquierdaFinal!=null)
                    defQ_0 = izquierdaFinal;
                else
                    defQ_0 = new Estado("S"+contadorEstados);
                estadosDef.add(defQ_0);
                if(defQ_0 != izquierdaFinal)
                    contadorEstados++;                
                Estado estadoFinalDef = new Estado("S"+contadorEstados);
                estadosFinalesDef.add(estadoFinalDef);
                estadosDef.add(estadoFinalDef);
                contadorEstados++;
                funcionesDef.add(new Funcion(defQ_0, raiz.darContenido(), estadoFinalDef));                
                Automata car = new Automata(defQ_0, estadosDef, estadosFinalesDef, funcionesDef, leng, Automata.AFN);
                return car;
        }                       
    }
    
    public boolean simulacionAFN(String w, Automata AFN)
    {        
        ArrayList<Estado> s_0 = new ArrayList();
        s_0.add(AFN.estadoInicial);
        ArrayList<Estado> s = AFN.cerraduraEpsilon(s_0);
        for(int i = 0; i < w.length(); i++)
        {
            s = AFN.cerraduraEpsilon(AFN.mover(s, w.charAt(i) + ""));                        
        }
        boolean centinela = false;
        for(int u = 0; u < s.size() && !centinela; u++)
        {
            for(int b = 0; b < AFN.estadosFinales.size() && !centinela; b++)
            {
                if(s.get(u).equals(AFN.estadosFinales.get(b)))                    
                    centinela = true;
            }
        }
        return centinela;
    }
    
    public ArrayList simulacionAFD(String w, Automata AFD)
    {
        ArrayList tokens = new ArrayList();        
        Estado eInicial = AFD.estadoInicial;
        ArrayList<Estado> res = new ArrayList();
        res.add(eInicial);
        ArrayList<Estado> s = AFD.cerraduraEpsilon(res);
        Estado ultimaAceptacion = null;
        Funcion ultimaFunc = null;
        int ultimoInt = 0;
        for(int i = 0; i < w.length(); i++)
        {
            s = (ArrayList) AFD.cerraduraEpsilon(AFD.mover(s, w.charAt(i)+"")).get(0);
            Funcion funcPiv = (Funcion) AFD.cerraduraEpsilon(AFD.mover(s, w.charAt(i)+"")).get(1);
            if(AFD.estadosFinales.contains(s.get(0)))
            {
                ultimaAceptacion = s.get(0);
                ultimaFunc = funcPiv;
                ultimoInt = i;
            }
        }
        boolean aceptado = false;
        for(int u=0; u<AFD.estadosFinales.size() && !aceptado; u++)
        {
            if(s.contains(AFD.estadosFinales.get(u)))
                aceptado = true; 
        }
        tokens.add(ultimoInt);
        tokens.add(ultimaAceptacion);
        tokens.add(ultimaFunc);
        return tokens; 
    }
    
    public boolean anulable(Node nodo)
    {
        switch (nodo.darContenido())
        {
            case "¬":
                return true;
            case "|":
                if(anulable(nodo.darHijoDerecho()) || anulable(nodo.darHijoIzquierdo()))
                    return true;
                else
                    return false;
            case ".":
                if(anulable(nodo.darHijoDerecho()) && anulable(nodo.darHijoIzquierdo()))
                    return true;
                else
                    return false;
            case "*":
                return true;
            default:
                return false;           
        }
    }
    
    public ArrayList<Integer> primeraPos(Node n) //TODO Review the pp part. It could be duplicates
    {
        switch (n.darContenido())
        {
            case "¬":
                ArrayList<Integer> vacio = new ArrayList();
                return vacio;
            case "|":                
                ArrayList<Integer> primeraPosIzq = primeraPos(n.darHijoIzquierdo());
                ArrayList<Integer> primeraPosDer = primeraPos(n.darHijoDerecho());
                ArrayList<Integer> arrayUnion = primeraPosDer;                
                for(int i = 0; i < primeraPosIzq.size(); i++)
                {
                    boolean existe = false;
                    for(int u = 0; u < arrayUnion.size() && !existe; u++)
                    {
                        if(primeraPosIzq.get(i).equals(arrayUnion.get(u)))
                            existe = true;                            
                    }
                    if(!existe)
                        arrayUnion.add(primeraPosIzq.get(i));
                    
                }
                return arrayUnion;
            case ".":
                ArrayList<Integer> primeraPIzq = primeraPos(n.darHijoIzquierdo());
                ArrayList<Integer> primeraPDer = primeraPos(n.darHijoDerecho());
                ArrayList<Integer> arrayU = primeraPDer; 
                if(anulable(n.darHijoIzquierdo()))
                {                                   
                    for(int i = 0; i < primeraPIzq.size(); i++)
                    {
                        boolean existe = false;
                        for(int u = 0; u < arrayU.size() && !existe; u++)
                        {
                            if(primeraPIzq.get(i).equals(arrayU.get(u)))
                                existe = true;                            
                        }
                        if(!existe)
                            arrayU.add(primeraPIzq.get(i));                        
                    }
                    return arrayU;
                }
                else
                    return primeraPIzq;
            case "*":
                return primeraPos(n.darHijoIzquierdo());
            default:                
                ArrayList<Integer> i = new ArrayList();                
                if(!pp.containsValue(n))
                {
                    i.add(pp.size());
                    pp.put(pp.size(),n);
                    return i;                
                }
                else
                {                    
                    for(Object o : pp.keySet())
                    {
                        if(pp.get(o).equals(n))
                        {                        
                            i.add((Integer) o);                           
                        }
                    }
                }
                return i;
        }
    }
    
    public ArrayList<Integer> ultimaPos(Node n)
    {
        switch(n.darContenido())
        {
            case "¬":
                ArrayList<Integer> vacio = new ArrayList();
                return vacio;
            case "|":
                ArrayList<Integer> ultimaPosIzq = ultimaPos(n.darHijoIzquierdo());
                ArrayList<Integer> ultimaPosDer = ultimaPos(n.darHijoDerecho());
                ArrayList<Integer> arrayUnion = ultimaPosDer;                
                for(int i = 0; i < ultimaPosIzq.size(); i++)
                {
                    boolean existe = false;
                    for(int u = 0; u < arrayUnion.size() && !existe; u++)
                    {
                        if(ultimaPosIzq.get(i).equals(arrayUnion.get(u)))
                            existe = true;                            
                    }
                    if(!existe)
                        arrayUnion.add(ultimaPosIzq.get(i));
                    
                }
                return arrayUnion;
            case ".":
                ArrayList<Integer> ultimaPIzq = ultimaPos(n.darHijoIzquierdo());
                ArrayList<Integer> ultimaPDer = ultimaPos(n.darHijoDerecho());
                ArrayList<Integer> arrayU = ultimaPDer; 
                if(anulable(n.darHijoDerecho()))
                {                                   
                    for(int i = 0; i < ultimaPIzq.size(); i++)
                    {
                        boolean existe = false;
                        for(int u = 0; u < arrayU.size() && !existe; u++)
                        {
                            if(ultimaPIzq.get(i).equals(arrayU.get(u)))
                                existe = true;                            
                        }
                        if(!existe)
                            arrayU.add(ultimaPIzq.get(i));                        
                    }
                    return arrayU;
                }
                else
                    return ultimaPDer;
            case "*":
                return (ultimaPos(n.darHijoIzquierdo()));
            default:
                ArrayList<Integer> i = new ArrayList();
                boolean found = false; 
                for(Object o : pp.keySet())
                {
                    if(pp.get(o).equals(n) && !found)
                    {                        
                        i.add((Integer) o);
                        found = true;
                    }
                }
                return i;
        }
    }
    
    public boolean siguientePos(Node n)
    {
        if(n!=null)
        {
            switch (n.darContenido())
            {
                case ".":
                    ArrayList<Integer> upIzq = ultimaPos(n.darHijoIzquierdo());
                    ArrayList<Integer> ppDer = primeraPos(n.darHijoDerecho());                    
                    for(int i = 0; i < upIzq.size(); i++)
                    {                        
                        if(sp.containsKey(upIzq.get(i)))
                        {
                            ArrayList<Integer> v = (ArrayList) sp.get(upIzq.get(i));
                            for(int rep = 0; rep < v.size() ; rep++)
                            {
                                if(!ppDer.contains(v.get(rep)))
                                    ppDer.add(v.get(rep));                                    
                            }              
                            sp.put(upIzq.get(i), ppDer);
                        }
                        else      
                        {
                            sp.put(upIzq.get(i), ppDer);                    
                        }
                    }
                    siguientePos(n.darHijoIzquierdo());
                    siguientePos(n.darHijoDerecho());
                    return true;
                case "*":
                    ArrayList<Integer> upN = ultimaPos(n);
                    ArrayList<Integer> ppN = primeraPos(n);
                    for(int u = 0; u < upN.size(); u++)
                    {
                        if(sp.containsKey(upN.get(u)))
                        {
                            ArrayList<Integer> p = (ArrayList) sp.get(upN.get(u));
                            for(int rept = 0; rept < p.size(); rept++)
                            {
                                if(!ppN.contains(p.get(rept)))
                                    ppN.add(p.get(rept));
                            }                            
                            sp.put(upN.get(u), ppN);
                        }
                        else
                        {
                            sp.put(upN.get(u), ppN);                    
                        }
                    }
                    siguientePos(n.darHijoIzquierdo());
                    return true;
                default:
                    siguientePos(n.darHijoIzquierdo());
                    siguientePos(n.darHijoDerecho());
                    return false;
            }
        }
        else
            return false;                  
    }
    
    public Automata construccionDirecta(Node n, ArrayList<String> leng) //TODO ALL
    {        
        ArrayList<Estado> Q = new ArrayList();
        ArrayList<Funcion> funcs = new ArrayList();
        ArrayList<Estado> eFinales = new ArrayList();
        Estado eInicial = new Estado("0");       
        HashMap equivalencias = new HashMap();
        ArrayList<Integer> ppInicial = primeraPos(n);
        equivalencias.put(eInicial, ppInicial);       
        siguientePos(n);       
        for(int i = 0; i < equivalencias.size(); i++)
        {
            //Parte en la que se localiza la siguiente Key a utilizar. 
            Iterator todos = equivalencias.keySet().iterator();   
            Estado estadoS = null;
            boolean salir = false;                        
            while(todos.hasNext() && !salir)
            {                
                Estado pivot = (Estado) todos.next();
                if(pivot.valor.equals(Integer.toString(i)))
                {
                    estadoS = pivot;
                    salir = true; 
                }
            }
            ArrayList<Integer> s = (ArrayList) equivalencias.get(estadoS);
            
            for(int u=0; u<leng.size();u++)
            {
                ArrayList<Integer> res = new ArrayList();
                for(int w = 0; w < s.size(); w++)
                {
                    Node nod = (Node) pp.get(s.get(w));
                    if(nod.darContenido().equals(leng.get(u)))
                        res.addAll((ArrayList) sp.get(s.get(w)));
                }
                if(!equivalencias.containsValue(res) && !res.isEmpty())                    
                {
                    Estado e = new Estado(Integer.toString(equivalencias.size()));
                    equivalencias.put(e, res);
                    funcs.add(new Funcion(estadoS, leng.get(u), e));
                }
                else
                {
                    Iterator en = equivalencias.keySet().iterator();
                    while(en.hasNext())
                    {
                        Estado es = (Estado) en.next();
                        if(compararArrays(((ArrayList) equivalencias.get(es)), res))
                            funcs.add(new Funcion(estadoS, leng.get(u), es));
                    }
                }
            }                      
        }
        Iterator lastLoop = equivalencias.keySet().iterator();
        while(lastLoop.hasNext())
        {            
            Estado est = (Estado) lastLoop.next();
            int fin = pp.size() - 1;                      
            ArrayList<Integer> aFinal = (ArrayList) equivalencias.get(est);
            if(aFinal.contains(fin))
                eFinales.add(est);
            Q.add(est);
            funcs.add(new Funcion(est, "¬", est));
        }
        return new Automata(eInicial, Q, eFinales, funcs, leng, Automata.AFD);
    }
    
    public boolean compararArrays(ArrayList a, ArrayList b)
    {        
        if(a.containsAll(b) && a.size()==b.size())
            return true;
        else
            return false;  
    }
    
    
    
    
    
    
    
    
    public boolean validarCadena(String cadena)
    {
        Pattern reg = Pattern.compile(           
            "^                # Anchor to start of string\n" +
            "[0-9A-Za-z+*$()|\\#¬]+  # Match one or more valid characters\n" +
            "$                # Anchor to end of string\n",
            Pattern.COMMENTS);
        Matcher m = reg.matcher(cadena);
        if (m.find() && checkParens(cadena)) 
        {
            System.out.print("OK: String has only valid characters and balanced parenthesis.\n");
            return true;
        }
        else 
        {
            System.out.print("ERROR: String has invalid characters or unbalanced parenthesis.\n");
            return false;//System.exit(0);
        }
    }
    
    public static Boolean checkParens(String s) {
        Pattern regex = Pattern.compile("\\(([^()]*)\\)");
        Matcher m = regex.matcher(s);
        // Loop removes matching nested parentheses from inside out.
        while (m.find()) {
            s = m.replaceFirst(m.group(1));
            m.reset(s);
        }
        regex = Pattern.compile("[()]");
        m = regex.matcher(s);
        // Check if there are any erroneous parentheses left over.
        if (m.find()) {
            return false;   // String has unbalanced parens.
        }
        return true;        // String has balanced parens.
    }
    
    public boolean isInteger( String input )  
    {  
       try  
       {  
          Integer.parseInt( input );  
          return true;  
       }  
       catch( Exception e)  
       {  
          return false;  
       }  
    }        
}
